Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 2
з дисципліни: “Алгоритми та методи обчислень”
на тему: “Розробка та дослідження ефективності методів пошуку даних”
Мета лабораторної роботи
Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
Теоретичні відомості
Одним з поширених прикладів застосування хеш-таблиць є побудова і пошук в таблиці ідентифікаторів програми. Головною характеристикою будь-якого елемента вхідної програми є його ім'я. Саме з іменами змінних, констант, функцій і інших елементів вхідної мови оперує розробник програми - тому і компілятор повинен вміти аналізувати ці елементи по їхніх іменах.
Таким чином, завдання компілятора полягає в тому, щоб зберігати деяку інформацію, пов'язану з кожним елементом вхідної програми, і мати доступ до цієї інформації за ім'ям елемента. Для рішення цього завдання компілятор організує спеціальні сховища даних, що називаються таблицями ідентифікаторів або таблицями символів. Таблиця ідентифікаторів складається з набору полів даних (записів), кожне з яких відповідає одному елементу вхідної програми. Запис містить всю необхідну компілятору інформацію про даний елемент і ця інформація може доповнюватись під час роботи компілятора. Кількість записів залежить від способу організації таблиці ідентифікаторів, але їх не може бути менше, ніж елементів у програмі. В принципі, компілятор може працювати не з однією, а з декількома таблицями ідентифікаторів - їх кількість і структура залежать від реалізації компілятора.
Компілятор поповнює записи в таблиці ідентифікаторів під час аналізу вхідної програми і знаходження в ній нових елементів, що вимагають розміщення в таблиці. Пошук інформації в таблиці виконується щоразу, коли компілятору потрібні відомості про той або інший елемент програми. Причому варто помітити, що пошук елемента в таблиці буде виконуватися компілятором значно частіше, ніж розміщення в ній нових елементів. Так відбувається тому, що опис нових елементів у вхідній програмі, як правило, зустрічаються набагато рідше, ніж ці елементи використовуються. Крім того, кожному додаванню елемента в таблицю ідентифікаторів завжди буде передувати операція пошуку - щоб переконатися, що такого елемента в таблиці немає.
Індивідуальне завдання
Варіант 12
Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць.
h(key) = [7*(кількість символів в ключі)] % m;
Розв'язання колізій при хешуванні здійснити квадратичного зондування з функцією повторного хешування:
hi(key) = ( h(key) + 3 · i 2 ) % m;
Вміст файлу “data.txt”:
Mazurenko Stanislav Volodymyrovych 04 11 1997 MTS 0 9 9 6 7 5 3 3 9 7 Lvivska Lviv Vidkryta 1 601 IKTA EOM KI-24 08 03 2016
Код програми
#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;
const int n = 28;
const int m = 37;
inline int hash_func_1()
{
return n % m;
}
inline int hash_func_2(int index)
{
return (hash_func_1() + 3 * index * index) % m;
}
inline int hash_func_3(int index)
{
return (hash_func_1() + index) % m;
}
void print_hash_table(char array[m][n])
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << array[i][j];
}
cout << endl;
}
}
void main()
{
char hash_table_1[m][n];
char hash_table_2[m][n];
char buffer[n][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
hash_table_1[i][j] = NULL;
hash_table_2[i][j] = NULL;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
...
